import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Test1 {
    //leetcode 移掉k位数字
    //https://leetcode.cn/problems/remove-k-digits/?envType=problem-list-v2&envId=greedy
    /**
     * 自己想的，过了百分之五十的测试用例
     * @param num
     * @param k
     * @return
     */
    public String removeKdigits1(String num, int k) {
        int len = num.length();
        if (k >= len) return "0";
        //先将去掉每一位之后形成的字符串记录下来，然后对其进行排序，从低到高排序，然后依次删除k位
        Integer[][] arr = new Integer[len][2];
        for (int i = 0; i < len; i++) {
            StringBuilder sb = new StringBuilder(num);
            sb.deleteCharAt(i);
            arr[i][0] = i;
            arr[i][1] = Integer.valueOf(sb.toString());
        }
        Arrays.sort(arr,(a,b) -> a[1]-b[1]);
        boolean[] hash = new boolean[len];
        for (int i = 0; i < k; i++) {
            hash[arr[i][0]] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            if (!hash[i]) sb.append(num.charAt(i));
        }
        return String.valueOf(Integer.valueOf(sb.toString()));
    }

    /**
     * 通过单调栈动态的构建字符串
     * @param num
     * @param k
     * @return
     */
    public String removeKdigits(String num, int k) {
        if (k >= num.length()) return "0";
        //遍历num字符串的每一个字符，然后将该字符放入单调栈中
        //如果当前要放入的字符小于栈顶的字符，并且删除的次数小于k，那么就删除栈顶的元素，并且继续
        //和栈顶的元素进行比较
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && c < stack.peekLast()) {
                stack.pollLast();
                k--;
            }
            stack.addLast(c);
        }

        //如果此时k>0，那么就直接从栈顶删除k个元素就可以了
        while (k > 0) {
            stack.pollLast();
            k--;
        }

        //此时单调中存放的就是删除了k个字符的字符串
        //那么接下来就是处理前导零了
        while (!stack.isEmpty() && stack.peekFirst() == '0' && stack.size() > 1) stack.pollFirst();

        //构建结果字符串
        StringBuilder ret = new StringBuilder();
        while (!stack.isEmpty()) {
            ret.append(stack.pollFirst());
        }
        return ret.toString();
    }



    public static void main(String[] args) {
        Test1 test1 = new Test1();
        String s = "10200";
        System.out.println(test1.removeKdigits(s, 1));
    }
}
